package com.leetcode;

public class Leetcode079 {
    //solution 1: 回溯的方法
    //两层递归：1）按word长度len，每个字符调用一次 2）每个字符又向四个方向延伸
    public boolean exist(char[][] board, String word) {
        int h = board.length, w = board[0].length;
        boolean[][] visited = new boolean[h][w];
        for (int i = 0; i < h; i++) {
            for (int j = 0; j < w; j++) {
                //board中每一个位置都尝试一次
                if (check(board, visited, i, j, word, 0)) {
                    return true;
                }
            }
        }

        return false;
    }

    private boolean check(char[][] board, boolean[][] visited, int i, int j, String word, int k) {
        if (board[i][j] != word.charAt(k)) {
            return false;
        } else if (k == word.length() - 1) {
            return true;
        }

        boolean result = false;
        //根据DFS思想，先设置标志位
        visited[i][j] = true;

        //每一个位置再再根据“上下左右”的方向来延伸。
        int[][] directions = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
        for (int[] dir : directions)  {
            int newi = i+dir[0];
            int newj = j+dir[1];
            if ((newi >= 0 && newi < board.length) && (newj >= 0 && newj < board[0].length)
                    && !visited[newi][newj]) {
                if (check(board, visited, newi, newj, word, k + 1)) {
                    result = true;
                    break;
                }
            }

        }
        //根据DFS思想，分支尝试失败，清除标志位
        visited[i][j] = false;
        return result;
    }

    public static void main(String[] args) {
        Leetcode079 leetcode079 = new Leetcode079();
        char[][] board = {{'A', 'B', 'C', 'E'}, {'S', 'F', 'C', 'S'}, {'A', 'D', 'E', 'E'}};
        String word = "SEE";

        System.out.println(leetcode079.exist(board, word));
    }

}
